#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s1[10010];
char s2[1000010];
int net[10010];
int len1,len2;
void getnet()
{
	net[1] = 0;
	int i,t;
	i = 1,t = 0;
	while(i<=len1)
	{
		if(t==0||s1[i]==s1[t])
		{
			net[i+1] = t+1;
			i++;
			t++;
		}
		else
		{
			t = net[t];
		}
	}
}
int kmp()
{
	getnet();
	int i,j,ans;
	i = j = 1;
	ans = 0;
	while(j<=len2)
	{
		if(i==0||s1[i]==s2[j])
		{
			i++;
			j++;
		}
		else
		{
			i = net[i];
			printf("i = %d j = %d\n",i,j);
		} 
		if(i == len1 + 1)
		{
			i = 1;
			ans++;
		}
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s1+1);
		scanf("%s",s2+1);
		len1 = strlen(s1+1);
		len2 = strlen(s2+1);
		int ans = kmp();
		printf("%d\n",ans);
	}
}
